/*
 * Created on 15 avr. 2005 by Tudor.Ionescu@supelec.fr
 */
package clustering.implementations;
import java.util.ArrayList;
import java.util.Hashtable;
import org.w3c.dom.*;

import clustering.framework.*;
import clustering.testing.Debug;
/**
 * @author Tudor.Ionescu@supelec.fr

QuartetTreeComparer

This class is an implementation of a tree comparing method that counts the number of different quartets contained in two different phylogenetic trees, which are given as parameters to the Compare method.

 */
public class QuartetTreeComparer implements IClusterTreeComparer{
    QNode [] qNodes1 = null;
    QNode [] qNodes2 = null;
    Hashtable htPath1 = null;
    Hashtable htPath2 = null;
    public ArrayList consistentQuartets = null;
    
    public static void checkFullQuartetList(double [][] dm){
        ArrayList alQuartets = new ArrayList();
        for (int i = 0; i < dm.length; i++){
          for (int j = i+1; j < dm.length; j++){
            for (int k = j+1; k < dm.length; k++){
              for (int l = k+1; l < dm.length; l++){
                Quartet q1 = new Quartet(i,j,k,l,dm);
                alQuartets.add(q1);
                Quartet q2 = new Quartet(i,k,j,l,dm);
                alQuartets.add(q2);
                Quartet q3 = new Quartet(i,l,j,k,dm);
                alQuartets.add(q3);
              }
            }
          }
        }
    }
    
    public double Compare(Document xmlTree1, Document xmlTree2, double [][] dMatrix1, double [][] dMatrix2, String [] filesList1, String [] filesList2){
        qNodes1 = new QNode[2*dMatrix1.length-2];
        qNodes2 = new QNode[2*dMatrix1.length-2];
        //ArrayList alQuartets = Quartet.generateFullQuartetList(dMatrix1);
        QuartetTree qt1 = constructFromXmlDocument(xmlTree1,qNodes1);
        QuartetTree qt2 = constructFromXmlDocument(xmlTree2,qNodes2);
        
        int consistent = 0;
        htPath1 = new Hashtable();
        htPath2 = new Hashtable();
        //consistentQuartets = new ArrayList();
        //double Ct = 0;
        //for(int i=0;i<alQuartets.size();i++){
        int cq_count = 0;
        for (int i = 0; i < dMatrix1.length; i++){
            for (int j = i+1; j < dMatrix1.length; j++){
              for (int k = j+1; k < dMatrix1.length; k++){
                for (int l = k+1; l < dMatrix1.length; l++){
                  Quartet q1,q2;
                  if(i!=j && k!=l){
	                  q1 = new Quartet(i,j,k,l,dMatrix1);
	                  q2 = new Quartet(
	                          getList2IndexOf(filesList1[q1.nodes[0]],filesList2),
	                          getList2IndexOf(filesList1[q1.nodes[1]],filesList2),
	                          getList2IndexOf(filesList1[q1.nodes[2]],filesList2),
	                          getList2IndexOf(filesList1[q1.nodes[3]],filesList2),
	                          dMatrix2
	                      	);
	                  if(isConsistent(q1,qt1,htPath1,qNodes1) && isConsistent(q2,qt2,htPath2,qNodes2)){
	                      consistent++;
	                  }
                  }
                  
                  if(i!=k && j!=l){                  
	                  q1 = new Quartet(i,k,j,l,dMatrix1);
	                  q2 = new Quartet(
	                          getList2IndexOf(filesList1[q1.nodes[0]],filesList2),
	                          getList2IndexOf(filesList1[q1.nodes[1]],filesList2),
	                          getList2IndexOf(filesList1[q1.nodes[2]],filesList2),
	                          getList2IndexOf(filesList1[q1.nodes[3]],filesList2),
	                          dMatrix2
	                      	);
	                  if(isConsistent(q1,qt1,htPath1,qNodes1) && isConsistent(q2,qt2,htPath2,qNodes2)){
	                      consistent++;
	                  }
                  }
                  
                  if(i!=l && j!=k){
	                  q1 = new Quartet(i,l,j,k,dMatrix1);
	                  q2 = new Quartet(
	                          getList2IndexOf(filesList1[q1.nodes[0]],filesList2),
	                          getList2IndexOf(filesList1[q1.nodes[1]],filesList2),
	                          getList2IndexOf(filesList1[q1.nodes[2]],filesList2),
	                          getList2IndexOf(filesList1[q1.nodes[3]],filesList2),
	                          dMatrix2
	                      	);
	                  if(isConsistent(q1,qt1,htPath1,qNodes1) && isConsistent(q2,qt2,htPath2,qNodes2)){
	                      consistent++;
	                  }
                  }
                  cq_count++;
                }
              }
            }
          }
            
        //}
        // consistent quartets count
        
        return ((double)consistent/(double)cq_count)*100;
        /*
        QuartetTreeScorer qts = new QuartetTreeScorer();
        qts.ComputeScore(xmlTree1,dMatrix1);
        ArrayList qList1 = qts.consistentQuartets;
        qts.ComputeScore(xmlTree2,dMatrix2);
        ArrayList qList2 = qts.consistentQuartets;
        for(int i=0;i<qList1.size();i++){
            Quartet q1 = (Quartet)qList1.get(i);
            for(int j=0;j<qList2.size();j++){
                Quartet q2 = (Quartet)qList2.get(j);
                q2 = new Quartet(
                        getList2IndexOf(filesList2[q2.nodes[0]],filesList1),
                        getList2IndexOf(filesList2[q2.nodes[1]],filesList1),
                        getList2IndexOf(filesList2[q2.nodes[2]],filesList1),
                        getList2IndexOf(filesList2[q2.nodes[3]],filesList1),
                        dMatrix1
                    	);
                if(q1.equals(q2,dMatrix1)){
                    qList2.remove(j);
                    break;
                }
            }
        }
        return (1 - (double)qList2.size()/(double)qList1.size())*100;
        */
    }
    int getList2IndexOf(String token, String [] list2){
        for(int i=0;i<list2.length;i++){
            if(token.equalsIgnoreCase(list2[i])){
                return i;
            }
        }
        return -1;
    }
    
    int node_count;
    QuartetTree constructFromXmlDocument(Document xmlTree, QNode [] qNodes){
        QuartetTree qt = new QuartetTree();
        QNode qn = new QNode(-1,null,null,null,-1);
        Node xmlNode = xmlTree.getFirstChild();
        node_count = 0;
        for(int i=0;i<xmlNode.getChildNodes().getLength();i++){
			generateTree(xmlNode.getChildNodes().item(i),qn,qNodes);
		}
        if(xmlNode.getChildNodes().getLength()==2){
		    QNode n1 = qn.adj[0];
		    QNode n2 = qn.adj[1];
		    n1.adj[0] = n2;
		    n2.adj[0] = n1;
		    qt.root = n1;
		}else{
		    qNodes[node_count++]=qn;
		    qt.root = qn;
		}        
        return qt;
    }
    void generateTree(Node xmlNode, QNode n0, QNode [] qNodes){
        String sId = xmlNode.getAttributes().getNamedItem("id").getNodeValue();
		int id = Integer.parseInt(sId);
		QNode qn = new QNode(id,n0,null,null,-1);
		if(n0.adj[0]==null)n0.adj[0]=qn;
		else if(n0.adj[1]==null)n0.adj[1]=qn;
		else n0.adj[2]=qn;
		if(xmlNode.hasChildNodes()){
			for(int i=0;i<xmlNode.getChildNodes().getLength();i++){
				generateTree(xmlNode.getChildNodes().item(i),qn,qNodes);
			}			
		}
		qNodes[node_count++]=qn;
	}
    boolean isConsistent(Quartet q, QuartetTree qt, Hashtable htPath, QNode [] qNodes){
        QNode a = getNodeByLabel(q.nodes[0],qNodes);
        QNode b = getNodeByLabel(q.nodes[1],qNodes);
        QNode c = getNodeByLabel(q.nodes[2],qNodes);
        QNode d = getNodeByLabel(q.nodes[3],qNodes);
        if(htPath.get(a)==null){
        	htPath.put(a,qt.Dijkstra(a,qNodes));
        }
        if(htPath.get(b)==null){
        	htPath.put(b,qt.Dijkstra(b,qNodes));
        }
        if(htPath.get(c)==null){
        	htPath.put(c,qt.Dijkstra(c,qNodes));
        }
        if(htPath.get(d)==null){
        	htPath.put(d,qt.Dijkstra(d,qNodes));
        }
        ArrayList path1 = (ArrayList)((Hashtable)htPath.get(a)).get(b);
        ArrayList path2 = (ArrayList)((Hashtable)htPath.get(c)).get(d);
        if(path2==null || path1 == null){
        	return false;
        }
        for(int i=1;i<path1.size()-1;i++){
            QNode qn1 = (QNode)path1.get(i);
            for(int j=1;j<path2.size()-1;j++){
                QNode qn2 = (QNode)path2.get(j);
                if(qn1 == qn2)return false;
            }
        }
        return true;
    }
    QNode getNodeByLabel(int label,QNode [] qNodes){
        for(int i=0;i<qNodes.length;i++){
            QNode qn = qNodes[i];
            if(qn.label == label)return qn;
        }
        return null;
    }
}
